lab2: Memory Management
内存管理主要有下面两方面的功能：
- 内存分配，能够及时的分配和回收，知道哪些进程和内存相映射。
- 虚拟内存管理。
注意：特别留意本文页目录(page directory rentry)和页表(page table entry)。
本文主要围绕memlayout.h中的那张虚拟内存表和128MB实际物理内存映射进行展开，注意区别。
Part 1: Physical Page Management
这一部分需要做的是对物理内存的管理工作。
首先有函数i386_detect_memory()用来检查物理内存的大小。本实验检测出来能够使用的物理内存是128MB。并且是按照page为单元进行管理的，1 page=4096 Bytes。为什么是这个大小的空间进行内存的管理，其实和内存管理有关。一个32位的地址可以被这样 进行划分管理：
// A linear address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory | Page Table | Offset within Page |
// | Index | Index | |
// +----------------+----------------+---------------------+
// \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
// \---------- PGNUM(la) ----------/
//
可以看到，最后的12位就是页(page)内偏移，即2^12=4096Bytes大小。
exercise 1
在kern/pmap.c中，通过修改下面的函数，对物理内存进行管理：
boot_alloc()// 分配n bytes大小的空间，空间大小以PAGE大小向上取整。mem_init()(only up to the call tocheck_page_free_list(1))page_init()：// 将可使用的内存以链表的形式连接在一起。page_alloc(): // 分配一个空闲pagepage_free(): // 与上面的功能相反，收回一个空闲页。
boot_alloc(uint32_t n): 这个函数仅在系统建立虚拟内存映射系统的时候使用，后面所有的内存分配单位都是PAGE，并且使用page_alloc(尽管这个n也是向着PAGE大小为单位向上取整的。因此我们的代码如下：
// LAB 2: Your code here. result = nextfree; nextfree = ROUNDUP(nextfree+n, PGSIZE); if((uint32_t)nextfree-KERNBASE > (npages*PGSIZE)){ panic("OUT OF MEMORY"); } return result;
之后，为了能够更好的管理物理内存，我们需要对每一个物理页有管理的元数据，使得更好的进行索引和权限的管理。
pages = (struct PageInfo *)boot_alloc(npages * sizeof(struct PageInfo));
memset(pages, 0, npages * sizeof(struct PageInfo));
总共需要131072KB=128MB的物理内存需要管理，这个大小是i386_detect_memory()检测出来的。因此需要131072/4 = 32768个PageInfo进行管理，每一个PageInfo都会管理一个物理page，或者是管理PageInfo指向的物理page里面维护的内容是Page地址和权限。
物理内存的分布情况：
page_init()函数主要是将物理内存中空闲的部分以链表的形式存储起来进行分配和回收。
JOS将内存分成了四个部分。
其中前1MB的内存分成了三个部分+1MB之后的内容：
[0-4)KB：IDT表，BIOS structure （不可用）
[4-640)KB: base memory （可用）
[640,1024)KB:IO hole （不可用）
—————————————————————————————— 1MB
[1024, ...) （可用）
其中前面的1MB的内存是这样划分的，从lab1里面找来的结构：
+------------------+ <- 0x00100000 (1MB) [640,1024)KB:IO hole
| BIOS ROM | |
+------------------+ <- 0x000F0000 (960KB) |
| 16-bit devices, | |
| expansion ROMs | |IO hole
+------------------+ <- 0x000C0000 (768KB) |
| VGA Display | |
+------------------+ <- 0x000A0000 (640KB) [4-640)KB: base memory
| | |
| Low Memory | |base memory
| | |
+------------------+ <- 0x00000000 [0-4)KB：IDT表，BIOS structure
最后我们内存的分配情况如下：
红色阴影部分的内存不可以再分配使用了。
因此我们对元数据pages的初始化和页空闲链表page_free_list进行初始化代码如下：
size_t i;
//boot_alloc(0)获取之前分配到的空闲页的首地址
const size_t pages_in_use_end =
npages_basemem + 96 + ((uint32_t)boot_alloc(0) - KERNBASE) / PGSIZE;
// pages_in_use_end = 600;
cprintf("now in use: %d\n", pages_in_use_end);
//设置让第0页为使用
cprintf("%08x %08x\n", pages, (uint32_t)boot_alloc(0));
//第0页用于存放real-mode IDT (interrupt descriptor table)and BIOS structures
pages[0].pp_ref = 1;
for (i = 1; i < npages_basemem; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
// I/O
for (i = npages_basemem; i < pages_in_use_end; ++i){
pages[i].pp_ref = 1;
}
for (i = pages_in_use_end; i < npages; ++i) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
其中96的由来就是(1024-640)/4=96。
page_alloc(): 每次调用分配一个page, 返回值为一个PageInfo。
代码如下：
struct PageInfo *
page_alloc(int alloc_flags)
{
// Fill this function in
struct PageInfo *temp;
if(page_free_list == NULL){
return NULL;
}
temp = page_free_list;
page_free_list = temp->pp_link;
temp->pp_link = NULL;
if (alloc_flags & ALLOC_ZERO)
//因为所有的程序中的地址都是虚拟地址进行操作的，所以我们需要将真实的物理页面转换到虚拟地址下初始化
memset(page2kva(temp), 0, PGSIZE);
return temp;
}
page_free():
回收相应的物理页面到空闲页链表，代码如下：
void
page_free(struct PageInfo *pp)
{
// Fill this function in
// Hint: You may want to panic if pp->pp_ref is nonzero or
// pp->pp_link is not NULL.
if(pp->pp_ref != 0 || pp->pp_link != NULL)
panic("can't properly free page\n");
pp->pp_link = page_free_list;
page_free_list = pp;
}
Part 2: Virtual Memory
exercise 2
阅读相关的文章，了解页转换机制和页的保护机制。
其中我们需要特别关注其中的两节，是我们之后实验的预备知识：
Virtual, Linear, and Physical Addresses
这一部分讲到了虚拟地址是怎么进行的，我们只需要理解下面的图就行：
首先有一个寄存器CR3保存的是页目录的首地址，然后通过虚拟地址的高10位，即可找到页表开始位置。通过中间的10位+页表开始地址，即可找到具体的页地址。
其中DIR ENTRY32位我们都用来存PAGE TABLE的开始地址，由于一个页大小为4096Bytes，因此一共可以管理4096/4=1024项PAGE TABLE。PG TBL ENTRY我们的高20位用来存储PAGE FRAME ADDRESS，后面的12位用来维护具体PAGE的访问权限，如下图所示：
这也是page-level protection所重点说明的。
我们对其中的每一位进行具体的说明：
- P：PRESENT
当为0时，表示是一个无效的项：
一般我们的程序都会将其设置成1。
- R/W: READ/WRITE, Read-only access (R/W=0), Read/write access (R/W=1)
当在内核态的时候，所有的pages都是可读可写的，当在用户态的时候，用户态的可读可写，内核态的仅可读。
关于怎么做大不同权限的访问，下面的U/S就能表示该页是内核态程序，还是用户态程序。当系统动态运行的时候，通过判断CPL寄存器的值，就能知道此刻用户的状态。从而能够进行不同用户的权限控制。
- U/S：USER/SUPERVISOR, 目前该值的设置和CPL寄存器的值有关。若CPL=3，则是用户态，若是0，1，2则是内核态。
- D：Dirty位是硬件进行设置的。主要是当内存满了，根据该位判断是否将这个页面重新写入硬盘中。若为1则肯定需要将其写入到硬盘中的。
Page Translation Cache
为了加速上面的虚拟地址的映射的过程，系统会将其放入到高速缓存中，每当这些表有变化的时候，需要手动的进行刷新，刷新的方法有下面的两种方法：
- 用EAX更新CR3
- 进程空间切换的时候也会进行这样的操作。
最后对应到程序中的位的设置：
// Page table/directory entry flags.
#define PTE_P 0x001 // Present
#define PTE_W 0x002 // Writeable
#define PTE_U 0x004 // User
#define PTE_PWT 0x008 // Write-Through
#define PTE_PCD 0x010 // Cache-Disable
#define PTE_A 0x020 // Accessed
#define PTE_D 0x040 // Dirty
#define PTE_PS 0x080 // Page Size
#define PTE_G 0x100 // Global
exercise 3
Ctrl+a c 进入qemu的调试模式，使用xp/Nx address查看物理内存的内容，在GDB中查看虚拟地址的内存内容。
info mem
info pg: 可查看页目录和页表的映射
info pg可以查看页目录和每一项页目录下对应页表下内容，如图所示：
我们可以看到初始化的时候我们仅初始化了第0x0和第0x3c0(960)页目录项。与entrypgdir.c里面的映射关系是一致的：
__attribute__((__aligned__(PGSIZE)))
pde_t entry_pgdir[NPDENTRIES] = {
// Map VA's [0, 4MB) to PA's [0, 4MB)
[0]
= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P,
// Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
[KERNBASE>>PDXSHIFT]
= ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P + PTE_W
};
我们也观察到了960项多了一个PTE_W的权限，也是能够在截图中体现的。
但是，发现权限位多了很多的D和A的权限，怎么回事呢？
我们可以查阅相关的资料，发现主要是用在多核系统中，系统在读或者是写时，会主动的更新这些位，当这些页面需要置换的时候，那么需要将置有D的page写回到硬盘中。
(qemu) info mem
0000000000000000-0000000000400000 0000000000400000 -r-
00000000f0000000-00000000f0400000 0000000000400000 -rw
其实有差异也是上面的初始化代码有关的。
我们将页目录项0增加一个权限+PTE_W，编译后的结果为：
确实是从这里进行权限的控制的。从这个角度来看，内存读取权限是4MB（一个页目录项管理的内存大小）来进行管理的。然而实际上应该是以4KB大小进行管理的。
一旦系统进入保护模式，所有的指针都是虚拟地址。
由于在内核初始化的时候，我们有的时候既需要操纵虚拟地址，有时候也需要操纵物理地址。
尽管我们在程序中只能使用虚拟地址，但是为了表示的方便性，我们使用了uintptr_t 和physaddr_t来区分虚拟地址和物理地址，尽管它们的数值类型一致。
Q: 一下代码x类型：
mystery_t x;
char* value = return_a_pointer();
*value = 10;
x = (mystery_t) value;
是虚拟地址。
虚拟地址转物理地址没有什么好说的，有时候我们需要将物理地址转发为虚拟地址，比如：
struct PageInfo *
page_alloc(int alloc_flags)
{
// Fill this function in
struct PageInfo *temp;
if(page_free_list == NULL){
return NULL;
}
temp = page_free_list;
page_free_list = temp->pp_link;
temp->pp_link = NULL;
if (alloc_flags & ALLOC_ZERO)
memset(page2kva(temp), 0, PGSIZE);
return temp;
}
我们分配一个page的时候，能够知道其物理地址，但是因为只能操纵虚拟地址，于是我们我们又通过page2kva()将其转化为虚拟地址进行初始化。
Reference counting
主要是维护一个page被虚拟地址使用的次数。在后面的实验中，同一个物理地址(page)能够被多个虚拟地址同时映射，或者是多个用户态下的地址空间。
下面给出一个例子，从check_page()中摘选的片段进行说明：
struct PageInfo *pp0, *pp1;
assert((pp0 = page_alloc(0)));
assert((pp1 = page_alloc(0)));
assert(page_insert(kern_pgdir, pp1, 0x0, PTE_W) == 0);
assert(page_insert(kern_pgdir, pp1, (void*) PGSIZE, PTE_W) == 0);
assert(check_va2pa(kern_pgdir, 0) == page2pa(pp1));
assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp1));
assert(pp1->pp_ref == 2);
第一部分是初始化，第二部分分别是将0x0和0x400分别映射到了pp1。最后pp1被引用的次数就是2。
最后我们在内存中进行检查，发现确实如此：
0x3ff000是pp0页面的地址，里面存放的前两项就是pp1|PERM的值。
然后我们讨论一下页引用+1的操作都在哪些地方：
- pg directory entry若之前没有分配一个page，那么就会分配一个新的页，这个pg directory entry就会记录这个page的地址。
*pgdir_entry = (page2pa(new_page) | PTE_P | PTE_W | PTE_U);
++new_page->pp_ref;
- 每当虚拟地址和相关的页进行映射的时候，这个页的引用值会+1。
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm){
++pp->pp_ref;
}
Page Table Management
exercise 4
建立虚拟地址和物理页之间的映射关系。
依次完成下面的函数：
pgdir_walk() // boot_map_region() page_lookup() page_remove() page_insert()
前面我们主要维护了页的元数据PageInfo，并且将物理的页连接到了一起。下面，我们就需要将虚拟内存和物理内存建立联系。
pgdir_walk(pde_t *pgdir, const void *va, int create): 通过va高10位找到pg directory entry，若此时dir entry没有被初始化，则通过create来判断是否新建页。并且最后返回pg table entry。
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
// Fill this function in
pde_t *pgdir_entry = pgdir + PDX(va);
if (!(*pgdir_entry & PTE_P)) {
if (!create)
return NULL;
else {
struct PageInfo *new_page = page_alloc(1);
if (!new_page)
return NULL;
*pgdir_entry = (page2pa(new_page) | PTE_P | PTE_W | PTE_U);
++new_page->pp_ref;
}
}
return (pte_t *)(KADDR(PTE_ADDR(*pgdir_entry))) + PTX(va);
}
boot_map_region(kern_pgdir, 虚拟地址开始, 大小, 物理地址, 读取权限);：主要是通过地址区间，将虚拟地址和物理地址进行映射。
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
// Fill this function in
int offset;
pte_t *pgtable_entry;
for (offset = 0; offset < size; offset += PGSIZE, va += PGSIZE, pa += PGSIZE) {
pgtable_entry = pgdir_walk(pgdir, (void *)va, 1);
//pgtable_entry中存着一条物理地址，指向一个page。这个page里面指向具体的所有虚拟地址与物理地址的映射。需要的大小位1024*4KB = 4MB就能管理全部的映射关系。
*pgtable_entry = (pa | perm | PTE_P);
}
}
page_lookup(): 找到虚拟地址对应的页地址。
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
// Fill this function in
pte_t *pgtable_entry = pgdir_walk(pgdir, va, 0);
if (!pgtable_entry || !(*pgtable_entry & PTE_P))
return NULL;
if (pte_store)
*pte_store = pgtable_entry;
return pa2page(PTE_ADDR(*pgtable_entry));
}
page_remove(): 将虚拟地址建立的映射关系取消。
void
page_remove(pde_t *pgdir, void *va)
{
// Fill this function in
pte_t *pgtable_entry;
struct PageInfo *page = page_lookup(pgdir, va, &pgtable_entry);
if (!page)
return;
page_decref(page);
tlb_invalidate(pgdir, va);
*pgtable_entry = 0;
}
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm):
若该虚拟地址之前已经建立映射了，那么取消原来的映射关系（即将原来的pg table entry内容移除），并且将新的映射关系记录下来。
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
// Fill this function in
pte_t *pgtable_entry = pgdir_walk(pgdir, va, 1);
if (!pgtable_entry)
return -E_NO_MEM;
++pp->pp_ref;
if ((*pgtable_entry) & PTE_P) {
tlb_invalidate(pgdir, va);
page_remove(pgdir, va);
}
*pgtable_entry = (page2pa(pp) | perm | PTE_P);
*(pgdir + PDX(va)) |= perm;
return 0;
return 0;
}
Part 3: Kernel Address Space
JOS将32位的线性地址空间划分成了两个部分：用户环境和系统环境。它们之间的划分界限为ULIM。并且JOS为内核保存了256MB大小的空间（0xf0000000-0xffffffff=256MB，这就是说内核的空间了。注意不要和物理内存大小搞混了，实际上这个实验物理内存由QEMU进行设置的，与JOS无关，为128MB大小）。
Permissions and Fault Isolation
[ULIM, ): 只有内核能够访问
[UTOP,ULIM): 都能够读，但是不能够write。实际上是内核向用户态主动暴露一些系统的信息，方便用户态进行读取和调用。
[0, UTOP): 用户态可以自由的进行权限的控制。
Initializing the Kernel Address Space
exercise 5
完成
mem_init()里面函数功能，使得能够通过check_kern_pgdir()和check_page_installed_pgdir()。
根据memlayout.h里面的虚拟内存的分布，进行相应的映射。
根据注释，我们进行下面的从虚拟地址到物理地址的映射操作：
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
boot_map_region(kern_pgdir, KERNBASE, (0xffffffff-KERNBASE), 0, PTE_W);
Q2：page directory 里面的1024项哪些被初始化过了，初始化后的值分别是什么？
UVPT = 0xef400000 = 957项
UPAGE = 0xef000000 = 956项
KSTACKTOP - KSTKSIZE = 0xefff 8000 = 959项
KERNBASE = 0xf0000000 = 960项
因此我们初始了上面的若干项，得到下面新的page directory表格：
| Entry | Virtual Address | Points to (logically) |
|---|---|---|
| 1023 | 0xffc00000 | |
| ... | ||
| 960 | 0xf0000000 | KERNBASE |
| 959 | 0xefff 8000 | Kernel stack |
| 957 | 0xef400000 | Page directory |
| 956 | 0xef000000 | PageInfo array |
| ... | ||
| 0 | 0x00000000 | NULL |
Q3: 我们将内核和用户态放在了同一个地址空间，为什么用户态不能读或者写内核的内存？是什么机制保证了能够这样做？
用户态的程序不能够访问不带有PTE_U标志的页。这些权限访问的标志位在page table中。
Q4: 最大支持多大的物理内存？怎么算的？
前面多次提到，最大为4GB。
Q5: 我们使用了多少的内存空间来管理内存？进行具体的说明。
1 page direstory+1024pages+0x100000 PageInfo = 4KB+4*1024KB+8192KB = 12292KB = 12MB左右
Q6: 从什么时候开始EIP从低地址(1MB)转向高地址(KERNBASE)？什么使得EIP既能够在低地址运行，又能够在高地址运行？为什么这个转化是必要的？
执行了这个语句之后：
mov $relocated, %eax
f0100028: b8 2f 00 10 f0 mov $0xf010002f,%eax
jmp *%eax
f010002d: ff e0 jmp *%eax
这一点在lab1 exercise 7也做了详细的说明。
之所以既能够在高地址也能够在低地址执行，是因为高地址和低地址都通过一个表(lab1 中提到了)映射到了[0, 4MB)中。因为内核的代码都是在高地址进行的，这样能够留下更多的空间给用户态。
Address Space Layout Alternatives
本部分完全是拓展部分，怎样不使用内核代码在高地址，用户程序在低地址的结构，甚至内核空间是不固定的？有待进一步的去学习挖掘。
结果
遗留问题
Q：不同虚拟地址能够映射到同一物理地址？
可以。上面已经给出具体的例子。新的问题，系统是怎么知道进行内容的替换的，用完后还能够替换回来？
如果进行访存的操作，如果此刻虚拟地址指向的物理地址不是想要的内容，那么就进行刷盘的操作，否则就能够进行直接读取的操作。
/*
* Virtual memory map: Permissions
* kernel/user
*
* 4 Gig --------> +------------------------------+
* | | RW/--
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* : . :
* : . :
* : . :
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
* | | RW/--
* | Remapped Physical Memory | RW/--
* | | RW/--
* KERNBASE, ----> +------------------------------+ 0xf0000000 --+
* KSTACKTOP | CPU0's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| |
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* | CPU1's Kernel Stack | RW/-- KSTKSIZE |
* | - - - - - - - - - - - - - - -| PTSIZE
* | Invalid Memory (*) | --/-- KSTKGAP |
* +------------------------------+ |
* : . : |
* : . : |
* MMIOLIM ------> +------------------------------+ 0xefc00000 --+ = 0xf0000000-4096*1024
* | Memory-mapped I/O | RW/-- PTSIZE
* ULIM, MMIOBASE --> +------------------------------+ 0xef800000
* | Cur. Page Table (User R-) | R-/R- PTSIZE
* UVPT ----> +------------------------------+ 0xef400000
* | RO PAGES | R-/R- PTSIZE
* UPAGES ----> +------------------------------+ 0xef000000
* | RO ENVS | R-/R- PTSIZE
* UTOP,UENVS ------> +------------------------------+ 0xeec00000
* UXSTACKTOP -/ | User Exception Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebff000
* | Empty Memory (*) | --/-- PGSIZE
* USTACKTOP ---> +------------------------------+ 0xeebfe000
* | Normal User Stack | RW/RW PGSIZE
* +------------------------------+ 0xeebfd000
* | |
* | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* . .
* . .
* . .
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
* | Program Data & Heap |
* UTEXT --------> +------------------------------+ 0x00800000
* PFTEMP -------> | Empty Memory (*) | PTSIZE
* | |
* UTEMP --------> +------------------------------+ 0x00400000 --+
* | Empty Memory (*) | |
* | - - - - - - - - - - - - - - -| |
* | User STAB Data (optional) | PTSIZE
* USTABDATA ----> +------------------------------+ 0x00200000 |
* | Empty Memory (*) | |
* 0 ------------> +------------------------------+ --+
*
* (*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
* "Empty Memory" is normally unmapped, but user programs may map pages
* there if desired. JOS user programs map pages temporarily at UTEMP.
*/